package 题目集.hash.字符串哈希;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/check-if-dfs-strings-are-palindromes/description/
 */
public class demo05_判断DFS字符串是否是回文串 {
    @Test
    public void test() {
        int[] arr = {-1, 0, 0, 1, 1, 2};
        String str = "aababa";
        boolean[] answer = findAnswer(arr, str);
        System.out.println(Arrays.toString(answer));
    }

    /**
     * 思路：dfs+字符串哈希
     * 题目指定的dfs是后序
     * 构建树，跑一次dfs，构建出dfs序，并记录dfs序中，每个节点记录其最左节点的dfs序号，以及自己原来的编号。
     * 因为是后序，所以自己的dfs序号就是区间的右端点，最左子节点就是左端点。
     *
     * @param parent
     * @param s
     * @return
     */
    Node[] dfnode;
    int dfi;
    Node[] index;
    long[] leftHash;
    long[] rightHash;
    long[] base;
    long p = 131;

    public boolean[] findAnswer(int[] parent, String s) {
        index = new Node[parent.length];
        dfnode = new Node[parent.length];
        boolean[] res = new boolean[parent.length];
        leftHash = new long[parent.length + 2];
        rightHash = new long[parent.length + 2];
        base = new long[parent.length + 2];
        char[] chars = s.toCharArray();
        for (int i = 0; i < index.length; i++) {
            index[i] = new Node(i, chars[i]);
        }
        for (int i = 1; i < parent.length; i++) {
            index[parent[i]].children.add(index[i]);
        }
        dfs(index[0]);
        base[0] = 1;
        /*构建正向字符串哈希*/
        for (int i = 1; i <= parent.length; i++) {
            base[i] = base[i - 1] * p;
            leftHash[i] = leftHash[i - 1] * p + dfnode[i - 1].v;
        }
        /*构建反向的字符串哈希*/
        for (int i = parent.length; i > 0; i--) {
            rightHash[i] = rightHash[i + 1] * p + dfnode[i - 1].v;
        }
        /*dfnode[i].id原来的编号*/
        for (int i = 0; i < dfnode.length; i++) {
            res[dfnode[i].id] = check(dfnode[i].left + 1, i + 1);
        }
        return res;
    }

    public boolean check(int l, int r) {
        long lhash = leftHash[r] - leftHash[l - 1] * base[r - (l - 1)];
        long rhash = rightHash[l] - rightHash[r + 1] * base[r - (l - 1)];
        return lhash == rhash;
    }

    /**
     * 返回最左节点
     *
     * @return
     */
    public void dfs(Node cur) {
        for (Node child : cur.children) {
            dfs(child);
        }
        if (cur.children.isEmpty()) {
            cur.left = dfi;
        } else {
            cur.left = cur.children.get(0).left;
        }
        dfnode[dfi++] = cur;
    }

    static class Node {
        int id, left;
        char v;

        public Node(int id, char v) {
            this.id = id;
            this.v = v;
        }

        List<Node> children = new ArrayList<>();
    }
}
